原始题目：剑指 Offer 31. 栈的压入、弹出序列 (opens new window)

解题思路：

根据已有的压入序列，我们借助一个辅助栈 $S$，模拟压入。

压入过程中，使用索引 $k$ 来指向弹出序列，如果 k 指向的弹出元素和当前 $S$ 的栈顶元素相同，则将 $S$ 的栈顶元素弹出，$k$ 自增，否则继续将压入序列压入 $S$ 中。

如果压入序列遍历完了，$S$ 中还有数据，说明弹出序列不合法，否则 $S$ 应该为空。

验证函数

**传递参数：**压入序列 $pushed$，弹出序列 $popped$。

验证过程：

• 创建一个模拟栈 $S$，弹出元素的索引 $k$ 初始值为 $0$。
• 遍历 $pushed$，用 $num$ 表示当前压入元素
  • 将 $num$ 压入 $S$ 中。
  • 循环检查，当 $S$ 不为空时，检查 $S$ 的栈顶元素是否等于 $popped[k]$
    • 如果相等，则 $S$ 弹出栈顶元素，$k$ 自增
• 判断 $S$ 是否为空
  • $false$：$S$ 不为空，$popped$ 不合法；
  • $true$：$S$ 为空，$popped$ 合法

代码：

public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (pushed == null || popped == null
            || pushed.length == 0 || pushed.length != popped.length) {
        return true;
    }
    // helper 来模拟 pushed 的入栈
    Deque<Integer> helper = new LinkedList<>();
    int k = 0;
    for (int num : pushed) {
        // 模拟入栈
        helper.push(num);
        // 如果辅助栈不为空，检查辅助栈的栈顶元素，如果和弹出序列相等就弹出
        while (!helper.isEmpty() && helper.peek() == popped[k]) {
            helper.pop();
            k++;
        }
    }
    return helper.isEmpty();
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 为 $pushed$ 的长度，每个元素最多出入栈 $2$ 次，即最多共 $2N$ 次出入栈操作。
• 空间复杂度$O(N)$：$N$ 为 $pushed$ 的长度，辅助栈最多存储 $N$ 个元素。